package com.atguigu.sort;

/**
 * @author RuiKnag
 * @create 2021-05-22-20:56
 *
 * 这个思想是每一次都选取一定间隔的数字进行排序，然后缩小这个间隔
 */
public class ShellSort {
    public static void sort(int[] arr){
        //我们的间隔要可以使用质数，
        //或者我们的最大间隔长度为不超过数组的1/3长度
        int knumth=1;
        while (knumth<arr.length/3){
            knumth=3*knumth+1;
        }
        /*
        * 希尔排序我们在选择好间距之后，从前往后开始，每一个数都和前面有这个间距的数进行比较，前面的数字大于后面的数字就进行交换
        * 一轮之后缩小这个间距，直到间距为1
        * */
        for (int gap = knumth; gap >0 ; gap=(gap-1)/3) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j >gap-1 ; j-=gap) {
                    if(arr[j]<arr[j-gap]){
                        Swap.swap(arr,j,j-gap);
                    }
                }
            }
        }
    }
}
